Sliding Window

A comprehensive guide to sliding window algorithms and techniques for Data Structures and Algorithms.

Table of Contents

1. Introduction to Sliding Window
2. Fixed Size Window
3. Variable Size Window
4. String Pattern Matching
5. Advanced Sliding Window
6. Two Pointers vs Sliding Window
7. Multi-Window Techniques
8. Usage Examples

---

Introduction to Sliding Window

The sliding window technique is a powerful algorithmic approach used to solve problems involving subarrays, substrings, or sequences. Instead of using nested loops (O(n²)), it maintains a "window" that slides through the data structure in O(n) time.

When to Use Sliding Window

• Subarray/Substring problems with contiguous elements
• Optimization problems (maximum, minimum, target sum)
• Pattern matching in strings
• Problems with constraints on window size or content

Core Concept

// Basic sliding window template
function slidingWindowTemplate(arr) {
    let left = 0;
    let windowSum = 0;
    let result = 0;

    for (let right = 0; right < arr.length; right++) {
        // Expand window by including arr[right]
        windowSum += arr[right];

        // Contract window if needed
        while (/* condition to shrink window */) {
            windowSum -= arr[left];
            left++;
        }

        // Update result based on current window
        result = Math.max(result, windowSum);
    }

    return result;
}

---

Fixed Size Window

Fixed size sliding window problems have a predetermined window size k.

1. Maximum Sum Subarray of Size K

function maxSumSubarray(arr, k) {
    if (arr.length < k) return -1;

    let windowSum = 0;
    let maxSum = 0;

    // Calculate sum of first window
    for (let i = 0; i < k; i++) {
        windowSum += arr[i];
    }
    maxSum = windowSum;

    // Slide the window
    for (let i = k; i < arr.length; i++) {
        windowSum = windowSum - arr[i - k] + arr[i];
        maxSum = Math.max(maxSum, windowSum);
    }

    return maxSum;
}

Time Complexity: O(n) | Space Complexity: O(1)

2. Average of Subarrays of Size K

function findAverages(arr, k) {
    const result = [];
    let windowSum = 0;
    let windowStart = 0;

    for (let windowEnd = 0; windowEnd < arr.length; windowEnd++) {
        windowSum += arr[windowEnd];

        // If we've hit the window size
        if (windowEnd >= k - 1) {
            result.push(windowSum / k);
            windowSum -= arr[windowStart];
            windowStart++;
        }
    }

    return result;
}

3. Maximum in Each Window of Size K

function maxInWindow(arr, k) {
    const result = [];
    const deque = []; // Store indices

    for (let i = 0; i < arr.length; i++) {
        // Remove indices outside current window
        while (deque.length && deque[0] <= i - k) {
            deque.shift();
        }

        // Remove smaller elements from back
        while (deque.length && arr[deque[deque.length - 1]] <= arr[i]) {
            deque.pop();
        }

        deque.push(i);

        // Add to result if window is complete
        if (i >= k - 1) {
            result.push(arr[deque[0]]);
        }
    }

    return result;
}

🔧 Technique: Using deque (double-ended queue) for efficient maximum tracking!

4. First Negative in Each Window

function firstNegativeInWindow(arr, k) {
    const result = [];
    const negatives = []; // Store indices of negative numbers

    for (let i = 0; i < arr.length; i++) {
        // Remove indices outside current window
        while (negatives.length && negatives[0] <= i - k) {
            negatives.shift();
        }

        // Add current index if negative
        if (arr[i] < 0) {
            negatives.push(i);
        }

        // Add result if window is complete
        if (i >= k - 1) {
            result.push(negatives.length ? arr[negatives[0]] : 0);
        }
    }

    return result;
}

---

Variable Size Window

Variable size windows expand and contract based on conditions.

1. Longest Substring Without Repeating Characters

function lengthOfLongestSubstring(s) {
    const charSet = new Set();
    let left = 0;
    let maxLength = 0;

    for (let right = 0; right < s.length; right++) {
        // Shrink window until no repeating character
        while (charSet.has(s[right])) {
            charSet.delete(s[left]);
            left++;
        }

        charSet.add(s[right]);
        maxLength = Math.max(maxLength, right - left + 1);
    }

    return maxLength;
}

Time Complexity: O(n) | Space Complexity: O(min(m,n)) where m is charset size

2. Smallest Subarray with Sum Greater than Target

function smallestSubarraySum(arr, target) {
    let windowSum = 0;
    let minLength = Infinity;
    let windowStart = 0;

    for (let windowEnd = 0; windowEnd < arr.length; windowEnd++) {
        windowSum += arr[windowEnd];

        // Shrink window while sum >= target
        while (windowSum >= target) {
            minLength = Math.min(minLength, windowEnd - windowStart + 1);
            windowSum -= arr[windowStart];
            windowStart++;
        }
    }

    return minLength === Infinity ? 0 : minLength;
}

3. Longest Subarray with At Most K Distinct Characters

function longestSubstringWithKDistinct(s, k) {
    if (k === 0) return 0;

    const charCount = new Map();
    let left = 0;
    let maxLength = 0;

    for (let right = 0; right < s.length; right++) {
        const rightChar = s[right];
        charCount.set(rightChar, (charCount.get(rightChar) || 0) + 1);

        // Shrink window if we have more than k distinct characters
        while (charCount.size > k) {
            const leftChar = s[left];
            charCount.set(leftChar, charCount.get(leftChar) - 1);
            if (charCount.get(leftChar) === 0) {
                charCount.delete(leftChar);
            }
            left++;
        }

        maxLength = Math.max(maxLength, right - left + 1);
    }

    return maxLength;
}

4. Subarray with Target Sum

function subarraySum(arr, target) {
    let windowSum = 0;
    let windowStart = 0;

    for (let windowEnd = 0; windowEnd < arr.length; windowEnd++) {
        windowSum += arr[windowEnd];

        // Shrink window if sum exceeds target
        while (windowSum > target && windowStart <= windowEnd) {
            windowSum -= arr[windowStart];
            windowStart++;
        }

        // Check if we found target sum
        if (windowSum === target) {
            return [windowStart, windowEnd];
        }
    }

    return [-1, -1]; // Not found
}

5. Maximum Fruits in Baskets (At Most 2 Types)

function totalFruit(fruits) {
    const basketCount = new Map();
    let left = 0;
    let maxFruits = 0;

    for (let right = 0; right < fruits.length; right++) {
        basketCount.set(fruits[right], (basketCount.get(fruits[right]) || 0) + 1);

        // If more than 2 types, shrink window
        while (basketCount.size > 2) {
            basketCount.set(fruits[left], basketCount.get(fruits[left]) - 1);
            if (basketCount.get(fruits[left]) === 0) {
                basketCount.delete(fruits[left]);
            }
            left++;
        }

        maxFruits = Math.max(maxFruits, right - left + 1);
    }

    return maxFruits;
}

---

String Pattern Matching

Advanced sliding window techniques for string problems.

1. Permutation in String

function checkInclusion(s1, s2) {
    if (s1.length > s2.length) return false;

    const s1Count = new Map();
    const windowCount = new Map();

    // Count characters in s1
    for (const char of s1) {
        s1Count.set(char, (s1Count.get(char) || 0) + 1);
    }

    let left = 0;
    let matches = 0;

    for (let right = 0; right < s2.length; right++) {
        const rightChar = s2[right];

        // Expand window
        windowCount.set(rightChar, (windowCount.get(rightChar) || 0) + 1);
        if (windowCount.get(rightChar) === s1Count.get(rightChar)) {
            matches++;
        }

        // Shrink window if size exceeds s1 length
        if (right - left + 1 > s1.length) {
            const leftChar = s2[left];
            if (windowCount.get(leftChar) === s1Count.get(leftChar)) {
                matches--;
            }
            windowCount.set(leftChar, windowCount.get(leftChar) - 1);
            left++;
        }

        // Check if all characters match
        if (matches === s1Count.size) {
            return true;
        }
    }

    return false;
}

2. Find All Anagrams in String

function findAnagrams(s, p) {
    if (p.length > s.length) return [];

    const result = [];
    const pCount = new Map();
    const windowCount = new Map();

    // Count characters in p
    for (const char of p) {
        pCount.set(char, (pCount.get(char) || 0) + 1);
    }

    let left = 0;

    for (let right = 0; right < s.length; right++) {
        const rightChar = s[right];
        windowCount.set(rightChar, (windowCount.get(rightChar) || 0) + 1);

        // Shrink window if size exceeds p length
        if (right - left + 1 > p.length) {
            const leftChar = s[left];
            windowCount.set(leftChar, windowCount.get(leftChar) - 1);
            if (windowCount.get(leftChar) === 0) {
                windowCount.delete(leftChar);
            }
            left++;
        }

        // Check if current window is an anagram
        if (right - left + 1 === p.length && mapsEqual(windowCount, pCount)) {
            result.push(left);
        }
    }

    return result;
}

function mapsEqual(map1, map2) {
    if (map1.size !== map2.size) return false;
    for (const [key, value] of map1) {
        if (map2.get(key) !== value) return false;
    }
    return true;
}

3. Minimum Window Substring

function minWindow(s, t) {
    if (t.length > s.length) return "";

    const tCount = new Map();
    const windowCount = new Map();

    // Count characters in t
    for (const char of t) {
        tCount.set(char, (tCount.get(char) || 0) + 1);
    }

    let left = 0;
    let matches = 0;
    let minLength = Infinity;
    let minStart = 0;

    for (let right = 0; right < s.length; right++) {
        const rightChar = s[right];

        // Expand window
        windowCount.set(rightChar, (windowCount.get(rightChar) || 0) + 1);
        if (tCount.has(rightChar) && windowCount.get(rightChar) === tCount.get(rightChar)) {
            matches++;
        }

        // Contract window while we have all required characters
        while (matches === tCount.size) {
            // Update minimum window
            if (right - left + 1 < minLength) {
                minLength = right - left + 1;
                minStart = left;
            }

            const leftChar = s[left];
            if (tCount.has(leftChar) && windowCount.get(leftChar) === tCount.get(leftChar)) {
                matches--;
            }
            windowCount.set(leftChar, windowCount.get(leftChar) - 1);
            left++;
        }
    }

    return minLength === Infinity ? "" : s.substring(minStart, minStart + minLength);
}

🧠 Algorithm Insight: This is one of the most complex sliding window problems - master this and you'll handle most variations!

---

Advanced Sliding Window

1. Longest Repeating Character Replacement

function characterReplacement(s, k) {
    const charCount = new Map();
    let left = 0;
    let maxCount = 0;
    let maxLength = 0;

    for (let right = 0; right < s.length; right++) {
        charCount.set(s[right], (charCount.get(s[right]) || 0) + 1);
        maxCount = Math.max(maxCount, charCount.get(s[right]));

        // If replacements needed > k, shrink window
        if (right - left + 1 - maxCount > k) {
            charCount.set(s[left], charCount.get(s[left]) - 1);
            left++;
        }

        maxLength = Math.max(maxLength, right - left + 1);
    }

    return maxLength;
}

2. Max Consecutive Ones with K Flips

function longestOnes(nums, k) {
    let left = 0;
    let zeroCount = 0;
    let maxLength = 0;

    for (let right = 0; right < nums.length; right++) {
        if (nums[right] === 0) {
            zeroCount++;
        }

        // If zero count exceeds k, shrink window
        while (zeroCount > k) {
            if (nums[left] === 0) {
                zeroCount--;
            }
            left++;
        }

        maxLength = Math.max(maxLength, right - left + 1);
    }

    return maxLength;
}

3. Sliding Window Maximum with Deque

function maxSlidingWindow(nums, k) {
    const result = [];
    const deque = []; // Store indices in decreasing order of values

    for (let i = 0; i < nums.length; i++) {
        // Remove indices outside current window
        while (deque.length && deque[0] <= i - k) {
            deque.shift();
        }

        // Remove indices with smaller values
        while (deque.length && nums[deque[deque.length - 1]] <= nums[i]) {
            deque.pop();
        }

        deque.push(i);

        // Add maximum of current window to result
        if (i >= k - 1) {
            result.push(nums[deque[0]]);
        }
    }

    return result;
}

4. Substring with Concatenation of All Words

function findSubstring(s, words) {
    if (!s || !words || words.length === 0) return [];

    const result = [];
    const wordLen = words[0].length;
    const totalLen = wordLen * words.length;
    const wordCount = new Map();

    // Count word frequencies
    for (const word of words) {
        wordCount.set(word, (wordCount.get(word) || 0) + 1);
    }

    for (let i = 0; i <= s.length - totalLen; i++) {
        const windowCount = new Map();
        let j = 0;

        // Check each word in the window
        while (j < words.length) {
            const word = s.substring(i + j * wordLen, i + (j + 1) * wordLen);

            if (!wordCount.has(word)) break;

            windowCount.set(word, (windowCount.get(word) || 0) + 1);

            if (windowCount.get(word) > wordCount.get(word)) break;

            j++;
        }

        if (j === words.length) {
            result.push(i);
        }
    }

    return result;
}

---

Two Pointers vs Sliding Window

Understanding when to use each technique:

Two Pointers

// Used for sorted arrays, palindromes, pair problems
function twoSum(arr, target) {
    let left = 0;
    let right = arr.length - 1;

    while (left < right) {
        const sum = arr[left] + arr[right];
        if (sum === target) return [left, right];
        else if (sum < target) left++;
        else right--;
    }

    return [-1, -1];
}

Sliding Window

// Used for subarray/substring problems with contiguous elements
function maxSubarraySum(arr, k) {
    let windowSum = 0;
    let maxSum = 0;

    for (let i = 0; i < arr.length; i++) {
        windowSum += arr[i];

        if (i >= k - 1) {
            maxSum = Math.max(maxSum, windowSum);
            windowSum -= arr[i - k + 1];
        }
    }

    return maxSum;
}

When to Use Each

Two Pointers	Sliding Window
Sorted arrays	Contiguous subarrays
Pair/triplet problems	Substring problems
Palindrome checks	Window-based optimization
Meet-in-the-middle	Pattern matching

---

Multi-Window Techniques

1. Sliding Window with Multiple Constraints

function minWindowTwoArrays(s1, s2, s3) {
    // Find minimum window in s1 that contains all characters from s2 and s3
    const s2Count = new Map();
    const s3Count = new Map();

    for (const char of s2) s2Count.set(char, (s2Count.get(char) || 0) + 1);
    for (const char of s3) s3Count.set(char, (s3Count.get(char) || 0) + 1);

    const windowCount = new Map();
    let left = 0;
    let matches2 = 0, matches3 = 0;
    let minLength = Infinity;
    let result = "";

    for (let right = 0; right < s1.length; right++) {
        const char = s1[right];
        windowCount.set(char, (windowCount.get(char) || 0) + 1);

        if (s2Count.has(char) && windowCount.get(char) === s2Count.get(char)) matches2++;
        if (s3Count.has(char) && windowCount.get(char) === s3Count.get(char)) matches3++;

        while (matches2 === s2Count.size && matches3 === s3Count.size) {
            if (right - left + 1 < minLength) {
                minLength = right - left + 1;
                result = s1.substring(left, right + 1);
            }

            const leftChar = s1[left];
            if (s2Count.has(leftChar) && windowCount.get(leftChar) === s2Count.get(leftChar)) matches2--;
            if (s3Count.has(leftChar) && windowCount.get(leftChar) === s3Count.get(leftChar)) matches3--;

            windowCount.set(leftChar, windowCount.get(leftChar) - 1);
            left++;
        }
    }

    return result;
}

2. Overlapping Windows

function maxSumTwoWindows(arr, k1, k2) {
    const n = arr.length;
    if (n < k1 + k2) return 0;

    // Precompute maximum sum for k1-size window ending at each position
    const maxK1Left = new Array(n).fill(0);
    const maxK1Right = new Array(n).fill(0);

    let windowSum = 0;

    // Left to right for k1
    for (let i = 0; i < n; i++) {
        windowSum += arr[i];
        if (i >= k1 - 1) {
            maxK1Left[i] = windowSum;
            if (i > k1 - 1) {
                maxK1Left[i] = Math.max(maxK1Left[i], maxK1Left[i - 1]);
                windowSum -= arr[i - k1 + 1];
            }
        } else if (i > 0) {
            maxK1Left[i] = maxK1Left[i - 1];
        }
    }

    // Right to left for k1
    windowSum = 0;
    for (let i = n - 1; i >= 0; i--) {
        windowSum += arr[i];
        if (n - 1 - i >= k1 - 1) {
            maxK1Right[i] = windowSum;
            if (n - 1 - i > k1 - 1) {
                maxK1Right[i] = Math.max(maxK1Right[i], maxK1Right[i + 1]);
                windowSum -= arr[i + k1 - 1];
            }
        } else if (i < n - 1) {
            maxK1Right[i] = maxK1Right[i + 1];
        }
    }

    // Find maximum sum of two non-overlapping windows
    let maxSum = 0;
    windowSum = 0;

    for (let i = 0; i <= n - k2; i++) {
        windowSum += arr[i];
        if (i >= k2 - 1) {
            const currentK2Sum = windowSum;
            const leftMax = i - k2 >= 0 ? maxK1Left[i - k2] : 0;
            const rightMax = i + 1 < n ? maxK1Right[i + 1] : 0;

            maxSum = Math.max(maxSum, currentK2Sum + Math.max(leftMax, rightMax));
            windowSum -= arr[i - k2 + 1];
        }
    }

    return maxSum;
}

---

Usage Examples

console.log("=== Sliding Window Techniques Demo ===");

// Fixed size window
const arr1 = [2, 1, 5, 1, 3, 2];
console.log("Max sum subarray (k=3):", maxSumSubarray(arr1, 3)); // 9

// Variable size window
const s1 = "abcabcbb";
console.log("Longest substring without repeating:", lengthOfLongestSubstring(s1)); // 3

const arr2 = [2, 1, 2, 3, 4, 3, 1];
console.log("Smallest subarray sum >= 7:", smallestSubarraySum(arr2, 7)); // 2

// String pattern matching
const s2 = "eidbaooo";
const s3 = "ab";
console.log("Contains permutation of 'ab':", checkInclusion(s3, s2)); // true

const s4 = "ADOBECODEBANC";
const t1 = "ABC";
console.log("Minimum window substring:", minWindow(s4, t1)); // "BANC"

// Advanced techniques
const s5 = "ABAB";
console.log("Longest repeating char replacement (k=2):", characterReplacement(s5, 2)); // 4

const nums1 = [1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0];
console.log("Max consecutive ones (k=2):", longestOnes(nums1, 2)); // 6

const nums2 = [1, 3, -1, -3, 5, 3, 6, 7];
console.log("Sliding window maximum (k=3):", maxSlidingWindow(nums2, 3)); // [3, 3, 5, 5, 6, 7]

---

Time Complexity Summary

Problem Type	Time Complexity	Space Complexity
Fixed Size Window	O(n)	O(1)
Variable Size Window	O(n)	O(k) for hash map
String Pattern Matching	O(n + m)	O(m) for pattern
Sliding Window Maximum	O(n)	O(k) for deque
Multi-Window	O(n)	O(1) typically

---

Common Patterns to Remember

1. Fixed Window Template

for (let i = 0; i < arr.length; i++) {
    windowSum += arr[i];
    if (i >= k - 1) {
        // Process window
        result = Math.max(result, windowSum);
        windowSum -= arr[i - k + 1];
    }
}

2. Variable Window Template

let left = 0;
for (let right = 0; right < arr.length; right++) {
    // Expand window
    windowSum += arr[right];

    // Contract window while condition
    while (/* condition to shrink */) {
        windowSum -= arr[left];
        left++;
    }

    // Update result
    result = Math.max(result, right - left + 1);
}

3. Character Frequency Template

const charCount = new Map();
let left = 0, matches = 0;

for (let right = 0; right < s.length; right++) {
    charCount.set(s[right], (charCount.get(s[right]) || 0) + 1);

    if (charCount.get(s[right]) === targetCount.get(s[right])) {
        matches++;
    }

    // Shrink window logic...
}

4. Deque for Min/Max

const deque = [];
for (let i = 0; i < arr.length; i++) {
    // Remove out of window elements
    while (deque.length && deque[0] <= i - k) {
        deque.shift();
    }

    // Maintain order (max at front)
    while (deque.length && arr[deque[deque.length - 1]] <= arr[i]) {
        deque.pop();
    }

    deque.push(i);
}

---

Key Interview Tips

1. Identify the pattern: Look for subarray/substring with constraints
2. Choose the right variant: Fixed vs variable size window
3. Handle edge cases: Empty arrays, single elements, impossible cases
4. Use appropriate data structures: Hash maps for frequency, deque for min/max
5. Optimize space: Often O(1) space is possible with careful implementation
6. Test thoroughly: Use examples like [1,2,3], [], [1], and edge cases

Problem Recognition Checklist

Use Sliding Window when you see:

• ✅ "Subarray" or "Substring" in the problem
• ✅ "Contiguous" elements requirement
• ✅ "Maximum/Minimum" with size constraint
• ✅ "Contains all" or "exactly K" conditions
• ✅ Pattern matching in strings

Don't use Sliding Window for:

• ❌ Non-contiguous subsequences
• ❌ Problems requiring backtracking
• ❌ Tree or graph traversals
• ❌ Dynamic programming with overlapping subproblems